/**
 * @Author: lena
 * @Description:快速排序
 * @Version: 1.0.0
 * @Date: 2021/9/12 16:03
 */

package sort_array

func QuickSort(arr []int, start int, end int) {
	if start >= end {
		return
	}
	sign := arr[start]
	i := start
	j := end
	for i != j {
		for i < j && arr[j] >= sign {
			j--
		}
		if i < j && arr[j] < sign {
			arr[i] = arr[j]
			i++
		}
		for i < j && arr[i] <= sign {
			i++
		}
		if i < j && arr[i] > sign {
			arr[j] = arr[i]
			j--
		}
	}
	arr[i] = sign
	QuickSort(arr, start, i-1)
	QuickSort(arr, i+1, end)
}
